class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

root=TreeNode(3)
root.left=TreeNode(9)
root.right=TreeNode(20)
root.right.left=TreeNode(15)
root.right.right=TreeNode(7)
# root=TreeNode(1)
# root.right=TreeNode(2)
# root.left=TreeNode(2)
# root.left.right=TreeNode(3)
# root.left.left=TreeNode(3)
# root.left.left.left=TreeNode(4)
# root.left.left.right=TreeNode(4)

# root=TreeNode(1)
# root.right=TreeNode(2)
# root.right.right=TreeNode(3)


def dfs(root):
    #边界条件
    if root.left==None and root.right==None:
        return 1
    leftHeight=0
    rightHeight=0
    if root.left:
        leftHeight=dfs(root.left)
    if root.right:
        rightHeight=dfs(root.right)
    print("============================")
    print("左子树高度：",leftHeight)
    print("右子树高度：",rightHeight)
    #子树不是平衡树的情况
    if leftHeight==-1 or rightHeight==-1:
        return -1
    #直接返回-1的情况
    if abs(rightHeight-leftHeight)>1:
        return -1
    #较大的高度+1
    return max(leftHeight,rightHeight)+1
def isBalanced(root):
    if dfs(root)==-1:
        return False
    else:
        return True
print(isBalanced(root))